% Autor: Axel Mayorga 07422, Samuel Chavez 07351
% Fecha: 04/10/2011

% Given a chessboard, check if position is valid.
validPos(Pos, Width, Height) :- 0 =< Pos, Pos < (Width * Height).

% Given a start position and a chessboard, calculates its next position
% It takes into account the chessboard boundaries.
next(SPos, Width, Height, R) :-
             NuPos is (SPos + 1),
             validPos(NuPos, Width, Height),
             R is NuPos.

% Given a position (0 <= position < Width*Height) calculates its coordinates
% column and row.
getCoords(Pos, Width, Height, X, Y):-
             getCol(Pos, Width, Height, X) ,
             getRow(Pos, Width, Height, Y).

% Given a position and a chessboard's dimention, calculates row and col
getCol(Pos, Width, _, Col) :- Col is (Pos mod Width).
getRow(Pos, Width, _, Row) :- Row is (Pos // Width).

% Given chessboard and two queen-positions, check if they eat each other. 
% Each one of the next 4 predicates takes into account one of the possible
% directions to eat. Asumes valid pos. 
checkNomVertical(FirstPos, SecondPos, Width, Height):-
             getCoords(FirstPos, Width, Height, X1, _),
             getCoords(SecondPos, Width, Height, X2, _),
             X1 == X2.
checkNomHorizontal(FirstPos, SecondPos, Width, Height):-
             getCoords(FirstPos, Width, Height, _, Y1),
             getCoords(SecondPos, Width, Height, _, Y2),
             Y1 == Y2.
checkNomDiag1(FirstPos, SecondPos, Width, _):-
             getCoords(FirstPos, Width, Height, X1, Y1),
             getCoords(SecondPos, Width, Height, X2, Y2),
             K is (X2 - X1),
             K2 is (Y1 + K),
             Y2 == K2.
checkNomDiag2(FirstPos, SecondPos, Width, Height):-
             getCoords(FirstPos, Width, Height, X1, Y1),
             getCoords(SecondPos, Width, Height, X2, Y2),
             K is (X2 - X1),
             K2 is (Y1 - K),
             Y2 == K2.

% Given chessboard and two queen-positions, check if they eat each other,
% and returns in the fifth parammeter how it happened (vertical, horizontal,
% diagonal).
checkNomNom(FirstPos, SecondPos, Width, Height, v):-
             checkNomVertical(FirstPos, SecondPos, Width, Height), !.
checkNomNom(FirstPos, SecondPos, Width, Height, h):-
             checkNomHorizontal(FirstPos, SecondPos, Width, Height), !.
checkNomNom(FirstPos, SecondPos, Width, Height, d1):-
             checkNomDiag1(FirstPos, SecondPos, Width, Height), !.
checkNomNom(FirstPos, SecondPos, Width, Height, d2):-
             checkNomDiag2(FirstPos, SecondPos, Width, Height), !.
checkNomNom(_, _, _, _, false).

% Check if new position enters in confflict with previously reached chessboard
% state.
failNewPos(_, _, _, [], false):-fail.
failNewPos(NuPos, Width, Height, [FirstPos | _], R):-
             checkNomNom(NuPos, FirstPos, Width, Height, R1),
             R1 \= false,
             R = R1.
failNewPos(NuPos, Width, Height, [FirstPos | _], _):-
             checkNomNom(NuPos, FirstPos, Width, Height, R1),
             R1 == false,
             fail.
failNewPos(NuPos, Width, Height, [_ | OtherPos], R):-
             failNewPos(NuPos, Width, Height, OtherPos, R1),
             R1 \= false,
             R = R1.

% Given a full chessboard caracterization, check if no queen eats other queen.
failStatus(Width, Height, [FirstPos | OPos]) :-
             failNewPos(FirstPos, Width, Height, OPos, R),
             R \= false, !.
failStatus(Width, Height, [_| OPos]):-
             failStatus(Width, Height, OPos).

% Given a chessboard dim and it's state, try to find the answer for NumQueens.
% Returns a array with the queens positions if it exists
getSolNQueens(Width, Height, _, State, []) :-
             failStatus(Width, Height, State).
getSolNQueens(Width, Height, NumQueens, State, State) :-
             not(failStatus(Width, Height, State)),
             length(State, Len),
             Len >= NumQueens.
getSolNQueens(Width, Height, NumQueens, State, Solution):-
             MOne is (-1),
             length(State, Len),
             ToGoal is (NumQueens - Len),
             solveFrom(Width, Height, ToGoal, State, MOne, Solution).

% Given a chessboard characterization and a starting chessboard position, try
% to iterate from that position till find an answer.
solveFrom(Width, Height, 0, State, _, State):-
             not(failStatus(Width, Height, State)).
solveFrom(Width, Height, ToGoal, State, From, Solution) :-
             ToGoal \= 0,
             next(From, Width, Height, NuPos),
             not(failNewPos(NuPos, Width, Height, State, _)),
             NuGoal is (ToGoal - 1),
             append(State, [NuPos], NuState),
             solveFrom(Width, Height, NuGoal, NuState, From, Solution).
solveFrom(Width, Height, ToGoal, State, From, Solution) :-
             ToGoal \= 0,
             next(From, Width, Height, NuPos),
             %failNewPos(NuPos, Width, Height, State, _),
             solveFrom(Width, Height, ToGoal, State, NuPos, Solution).